/*
 * @lc app=leetcode id=10 lang=cpp
 *
 * [10] Regular Expression Matching
 */

class Solution
{
public:
    static const int FRONT=-1;
    bool isMatch(string s, string p) {
        int m = s.length(),n = p.length();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
        dp[0][0] = true;

        for (int j = 1; j <= n; j++)
            dp[0][j] = j > 1  && p[j-1] == '*' && dp[0][j-2];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                if (p[j-1] == '.' || p[j-1] == s[i-1])
                    dp[i][j] = dp[i-1][j-1];

                if (p[j-1] == '*') {
                    dp[i][j] = (j > 1 && dp[i][j-2]) || 
                        (dp[i-1][j] && (j > 1 && p[j-2] == '.' || p[j-2] == s[i-1]));
                }
            }
        }
        return dp[m][n];
    }
};
